/*
 * Copyright (C) 2025 ameise <ameise.wang@gmail.com> - All Rights Reserved
 *
 * This file is part of e3ds.
 *
 * e3ds is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * e3ds is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with e3ds. If not, see <https://www.gnu.org/licenses/>.
 */

package rtree

import (
	"math"
	"sync"
	"sync/atomic"
)

var nodePool = sync.Pool{
	New: func() any {
		atomic.AddUint64(&_gInstId, 1)
		return &node{
			id:       _gInstId,
			children: make(map[Tag]box, maxObject),
		}
	},
}

func newNode(h int) *node {
	n := nodePool.Get().(*node)
	n.father = nil
	n.height = h
	return n
}

func freeNode(n *node) {
	n.father = nil
	n.box.clean()
	n.height = 0
	nodePool.Put(n)
}

type node struct {
	id       Tag
	box      rect
	father   *node
	height   int
	children map[Tag]box
}

func (ts *node) UniqueID() Tag {
	return ts.id
}

func (ts *node) rect() *rect {
	return &ts.box
}

func (ts *node) areaCalc() {
	first := true
	for _, c := range ts.children {
		if first {
			ts.box.set(c.rect().min, c.rect().max)
			first = false
		} else {
			ts.box.merge(c.rect())
		}
	}
}

func (ts *node) setFather(f *node) {
	ts.father = f
}

func (ts *node) isOverlap(r *rect, withAdj bool, cb func(*Entity) bool) bool {
	if ts.box.isOverlap(r, withAdj) {
		for _, c := range ts.children {
			if !c.isOverlap(r, withAdj, cb) {
				return false
			}
		}
	}
	return true
}

func (ts *node) free() {
	if len(ts.children) > 0 {
		panic("free: too many children")
	}
	freeNode(ts)
}

func (ts *node) insert(obj *Entity) bool {
	if ts.height == 0 {
		ts.addChildren(obj)
		return ts.box.merge(obj.rect())
	}
	best := ts.chooseBest(obj.rect())
	grown := best.insert(obj)
	if grown {
		grown = ts.box.merge(obj.rect())
	}
	if len(best.children) == maxObject {
		nn := newNode(best.height)
		best.splitTo(nn)
		ts.addChildren(nn)
	}
	return grown
}

func (ts *node) delete(obj *Entity) {
	ts.delChildren(obj.UniqueID())
}

func (ts *node) addChildren(b box) {
	ts.children[b.UniqueID()] = b
	b.setFather(ts)
}

func (ts *node) delChildren(id Tag) {
	if c, ok := ts.children[id]; ok {
		delete(ts.children, id)
		ts.checkAreaCalc(c.rect())
		c.free()
		ts.tryDown()
	}
}

func (ts *node) checkAreaCalc(r *rect) {
	if ts.box.onEdge(r) {
		ts.areaCalc()
		if ts.father != nil {
			ts.father.checkAreaCalc(r)
		}
	}
}

func (ts *node) tryDown() {
	if ts.father != nil {
		if len(ts.children) == 0 {
			ts.father.delChildren(ts.id)
		} else {
			ts.father.tryMergeChildren(ts)
		}
	}
}

func (ts *node) tryMergeChildren(c *node) {
	if len(c.children) <= minObject {
		if _, ok := ts.children[c.id]; ok && len(ts.children) > 1 {
			delete(ts.children, c.id)
			best := ts.chooseBest(c.rect())
			if len(best.children) < halfMaxObject {
				for id, cc := range c.children {
					best.addChildren(cc)
					delete(c.children, id)
				}
				best.rect().merge(c.rect())
				c.free()
				ts.tryDown()
			} else {
				ts.children[c.id] = c
			}
		}
	}
}

func (ts *node) chooseBest(box *rect) (best *node) {
	selectDiff := math.Inf(1)
	for _, nn := range ts.children {
		nd := nn.(*node)
		c := nd.box.checkMergeRect(box)
		diff := c.area - nd.box.area

		if diff > selectDiff {
			continue
		}

		if diff == selectDiff {
			if best == nil {
				selectDiff = diff
				best = nd
				continue
			}
			if nd.box.area > best.box.area {
				continue
			}
			if nd.box.area == best.box.area {
				if len(nd.children) >= len(nd.children) {
					continue
				}
			}
		}
		selectDiff = diff
		best = nd
	}
	return
}

func (ts *node) splitTo(tn *node) {
	tn.box.set(ts.box.max, ts.box.max)
	ts.box.set(ts.box.min, ts.box.min)

	w := make(map[Tag]box, halfMaxObject)
	for id, c := range ts.children {
		nMin := ts.box.checkMergeRect(c.rect())
		nMax := tn.box.checkMergeRect(c.rect())
		if nMax.area > nMin.area {
			ts.box = nMin
			continue
		}
		if nMax.area == nMin.area {
			w[id] = c
		} else {
			delete(ts.children, id)
			tn.addChildren(c)
			tn.box = nMax
		}
	}
	for id, c := range w {
		if len(tn.children) < len(ts.children) {
			delete(ts.children, id)
			tn.addChildren(c)
			tn.box.merge(c.rect())
		} else {
			ts.box.merge(c.rect())
		}
	}
}
